package com.example.Arithmetic.Arithmetic;

/**
 * 日期：2024/1/2
 * 时间：8:43
 * 描述：卡特兰数，公式为C(3)*2+C(2)*2+C(1)
 */
public class Catalan {
    public static void main(String[] args) {
        System.out.println(catalan(3));
    }

    private static int catalan(int n) {
        int[] catalan = new int[n + 1];
        catalan[0] = 1;
        catalan[1] = 1;
        for (int i = 2; i < n+1; i++) {
//            外层循环,表示第几个数字
            for (int j = 0; j < i; j++) {
                catalan[i]+=catalan[j]*catalan[i-1-j];
            }
        }
        return catalan[n];
    }
}
